package 代码随想录_动态规划.子序列问题.编辑距离;

/**
 * @author zx
 * @create 2022-06-06 15:39
 * 组成部分一：确定状态
 *               最后一步：
 *               子问题：
 *               确定dp数组(dp table)以及下标的含义
 *               dp[i][j]表示以下标i-1为结尾的字符串word1,和以下标j-1为结尾的字符串word2,最近编辑距离为dp[i][j].
 * 组成部分一：确定状态
 * 最后一步：
 * 子问题：
 * 组成部分二：转移方程
 * 确定递推公式的时候,首先要考虑清楚编辑的几种操作,整理如下：
 * if (word1[i - 1] == word2[j - 1])   不操作
 * if (word1[i - 1] != word2[j - 1])   a.增   b.删   c.换
 * if (word1[i - 1] == word2[j - 1]) 那么说明不用任何编辑,dp[i][j] 就应该是 dp[i - 1][j - 1]
 * 即dp[i][j] = dp[i - 1][j - 1];
 * 此时可能有点不明白,为啥要即dp[i][j] = dp[i - 1][j - 1]呢？
 * 那么就在回顾上面讲过的dp[i][j]的定义,word1[i - 1] 与 word2[j - 1]相等了,那么就不用编辑了
 * 以下标i-2为结尾的字符串word1和以下标j-2为结尾的字符串word2的最近编辑距离dp[i - 1][j - 1]就是dp[i][j]
 * 组成部分三：初始条件和边界情况
 * 组成部分四：计算顺序
 */
public class 编辑距离_72 {
    /**
     * @return 编辑距离的转移方程的推导过程思维有点复杂,看代码随想录
     * 背
     */
    public int minDistance(String word1, String word2) {
        //dp[i][j] 表示以下标i-1为结尾的字符串word1,和以下标j-1为结尾的字符串word2
        //最近编辑距离为dp[i][j]
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        for(int i = 0;i <= word1.length();i++) dp[i][0] = i;
        for(int j = 0;j <= word2.length();j++) dp[0][j] = j;
        for(int i = 1;i <= word1.length();i++){
            for(int j = 1;j <= word2.length();j++){
                if(word1.charAt(i - 1) == word2.charAt(j - 1)){
                    dp[i][j] = dp[i - 1][j - 1];
                }else{
                    dp[i][j] = Math.min(dp[i - 1][j - 1] + 1,
                            Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
                }
            }
        }
        return dp[word1.length()][word2.length()];
    }
}
